﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions.Problems
{
    /*
     * A number consisting entirely of ones is called a repunit. We shall define R(k) to be a repunit of length k; for example, R(6) = 111111.

Given that n is a positive integer and GCD(n, 10) = 1, it can be shown that there always exists a value, k, for which R(k) is divisible by n, and let A(n) be the least such value of k; for example, A(7) = 6 and A(41) = 5.

You are given that for all primes, p > 5, that p − 1 is divisible by A(p). For example, when p = 41, A(41) = 5, and 40 is divisible by 5.

However, there are rare composite values for which this is also true; the first five examples being 91, 259, 451, 481, and 703.

Find the sum of the first twenty-five composite values of n for which
GCD(n, 10) = 1 and n − 1 is divisible by A(n).

     * */
    class Problem130 : IProblem
    {
        public string Calculate()
        {
            int[] lookup = new int[]
            {
                1, 2, 3, 4, 5, 6, 7, 8, 9, //1
                0, 0, 0, 0, 0, 0, 0, 0, 0,
                7, 4, 1, 8, 5, 2, 9, 6, 3, //3
                0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0, 
                3, 6, 9, 2, 5, 8, 1, 4, 7, //7
                0, 0, 0, 0, 0, 0, 0, 0, 0,
                9, 8, 7, 6, 5, 4, 3, 2, 1  //9
            };

            int target = 25;
            int count = 0;

            long sum = 0;

            long n = 1;

            SieveOfAtkin sieve = new SieveOfAtkin(1000000);


            while (true)
            {
                n += 2;
                if (n % 5 == 0)
                    continue;

                long k = 0;
                long lookupN = n % 10;
                long result = 0;
                do
                {
                    result += lookup[(lookupN - 1) * 9 + (11 - result % 10) % 10 - 1] * n;

                    while (result % 10 == 1)
                    {
                        k++;
                        result /= 10;
                    }
                } while (result > 0);

                if (!sieve.IsPrime(n))
                    if ((n - 1) % k == 0)
                    {
                        count++;
                        sum += n;
                        Console.WriteLine(n);
                        if (count == target)
                            return sum.ToString();
                    }
            }
        }
    }
}
